﻿#include "Heap.h"

// 堆-工具函数
// 数据交换
void Swap(DataType* arr, int x, int y)
{
	DataType tmp = arr[x];
	arr[x] = arr[y];
	arr[y] = tmp;
}
// 容量检查 / 扩容操作
void CheckCapacity(Heap* heap)
{
	if (heap->_capacity == heap->_size)
	{
		heap->_capacity *= 2;
		heap->_a = (DataType*)realloc(heap->_a, sizeof(DataType) * heap->_capacity);
	}
}
// 向下调整
void AdjustDown(DataType* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && arr[child + 1] < arr[child])
		{
			child++;
		}
		if (arr[child] < arr[parent])
		{
			Swap(arr, child, parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// 向上调整
void AdjustUp(DataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[parent] > arr[child])
		{
			Swap(arr, parent, child);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
// 小堆判断函数 - 是则返回1 不是返回0
int SmallHeapCheck(DataType* arr, int parent, int n)
{
	int left = parent * 2 + 1;
	int right = left + 1;

	if (left < n && (arr[left] > arr[parent] || !SmallHeapCheck(arr, left, n))) return 0;
	if (right < n && (arr[right] > arr[parent] || !SmallHeapCheck(arr, right, n))) return 0;
	return 1;
}


// 堆-基本操作函数
// 堆-初始化
void HeapInit(Heap* heap, DataType* arr, int n)
{
	assert(heap);
	heap->_a = (DataType*)malloc(sizeof(DataType) * n);
	memcpy(heap->_a, arr, sizeof(DataType) * n);
	heap->_capacity = heap->_size = n;
	
	// 向下调整建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(heap->_a, n, i);
	}
}
// 堆-销毁
void HeapDestory(Heap* heap)
{
	assert(heap);
	free(heap->_a);
	heap->_capacity = heap->_size = 0;
}
// 堆-插入堆中
void HeapPush(Heap* heap, DataType elem)
{
	assert(heap);
	CheckCapacity(heap);
	heap->_a[heap->_size] = elem;
	AdjustUp(heap->_a, heap->_size);
	heap->_size++;
}
// 堆-删除堆顶
void HeapPop(Heap* heap)
{
	assert(heap);
	Swap(heap->_a, 0, heap->_size - 1);
	heap->_size--;
	AdjustDown(heap->_a, heap->_size, 0);
}
// 堆-获取堆顶元素
DataType HeapTop(Heap* heap)
{
	assert(heap);
	assert(!HeapEmpty(heap));
	return heap->_a[0];
}
// 堆-有效数据个数
size_t HeapSize(Heap* heap)
{
	assert(heap);
	return heap->_size;
}
// 堆-判空 为空返回非0 非空返回0
int HeapEmpty(Heap* heap)
{
	return heap->_size == 0;
}